#include "main/utils.h"
using namespace std;

class Solution {
  public:
    int trap1(vector<int>& height) {
      int len = height.size();
      vector<int> maxleft(len), maxright(len);
      int max_left = 0;
      for (int i = 0; i < len; ++i) {
        max_left = max(max_left, height[i]);
        maxleft[i] = max_left;
      }
      int max_right = 0;
      for (int i = len - 1; i >= 0; --i) {
        max_right = max(max_right, height[i]);
        maxright[i] = max_right;
      }
      int ans = 0;
      for (int i = 1; i < len - 1; ++i) {
        int min_val = min(maxleft[i], maxright[i]);
        if (height[i] < min_val) {
          ans += (min_val - height[i]);
        }
      }
      return ans;
    }
    int trap2(vector<int>& height) {
      int len = height.size();
      stack<int> stk;
      int total_area = 0;
      for (int i = 0; i < len; ++i) {
        while (!stk.empty() && height[i] > height[stk.top()]) {
          int top = stk.top();
          stk.pop();
          if (stk.empty()) {
            break;
          }
          int left = stk.top();
          int cur_width = i - left - 1;
          int cur_height = min(height[left], height[i]) - height[top];
          int cur_area = cur_width * cur_height;
          total_area += cur_area;
        }
        stk.push(i);
      }
      return total_area;
    }
    int trap3(vector<int>& height) {
      int len = height.size();
      int left = 0, right = len - 1;
      int leftmax = height[0], rightmax = height[len - 1];
      int maxarea = 0;
      while (left < right) {
        leftmax = max(leftmax, height[left]);
        rightmax = max(rightmax, height[right]);
        if (leftmax < rightmax) {
          maxarea += (leftmax - height[left]);
          ++left;
        } else {
          maxarea += (rightmax - height[right]);
          --right;
        }
      }
      return maxarea;
    }
};

int main() {
  vector<int> input = {0, 1, 0, 2, 1, 0, 1, 1, 2, 1, 2, 1};
  Solution su;
  cout << su.trap1(input) << endl;
  cout << su.trap2(input) << endl;
  cout << su.trap3(input) << endl;
}
